package NiuKe.Tree;

//牛客做题的二叉树
import java.util.*;

class TreeNode {
   int val = 0;
    TreeNode left = null;
    TreeNode right = null;
   public TreeNode(int val) {
      this.val = val;
    }
  }


public class Solution {

    /*二叉树的前序遍历
    1:给你二叉树的根节点 root ，返回它节点值的 前序 遍历。*/
   private void pre(List<Integer> list,TreeNode root){
       if (root==null)return ;
       list.add(root.val);
       pre(list,root.left);
       pre(list,root.right);

   }
    public int[] preorderTraversal (TreeNode root) {
        List<Integer> list=new ArrayList<>();
        pre(list,root);
        int[] array=new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            array[i]=list.get(i);
        }

        return array;
    }
    /*二叉树的中序遍历
   2:给你二叉树的根节点 root ，返回它节点值的 中序 遍历。*/
    private void pre2(List<Integer> list,TreeNode root){
        if (root==null)return ;
        pre2(list,root.left);
        list.add(root.val);
        pre2(list,root.right);

    }
    public int[] inorderTraversal (TreeNode root) {
        // write code here
        List<Integer> list=new ArrayList<>();
        pre2(list,root);
        int[] array=new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            array[i]=list.get(i);
        }
        return array;
    }
    /*二叉树的后序遍历
  3:给你二叉树的根节点 root ，返回它节点值的 后序 遍历。*/
    private void pre3(List<Integer> list,TreeNode root){
        if (root==null)return ;
        pre3(list,root.left);
        pre3(list,root.right);
        list.add(root.val);
    }
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        List<Integer> list=new ArrayList<>();
        pre3(list,root);
        int[] array=new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            array[i]=list.get(i);
        }
        return array;
    }
    /*二叉树的层次遍历
  4:给你二叉树的根节点 root ，返回它节点值的 层次 遍历。*/
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> arrayList=new ArrayList<>();
        if (root==null)return arrayList;
        Queue<TreeNode> queue=new LinkedList<>();//定义队列用来实现层序遍历
        queue.offer(root);

        while (!queue.isEmpty()){
            int size=queue.size();//这个值代表当前层有多少个节点
            ArrayList<Integer> list1=new ArrayList<>();
            while (size!=0){
                TreeNode cur=queue.poll();
                list1.add(cur.val);
                if (cur.left!=null)queue.offer(cur.left);
                if (cur.right!=null)queue.offer(cur.right);
                size--;
            }
            arrayList.add(list1);
        }
        return arrayList;
    }
    /* 按之字形顺序打印二叉树
    5：给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
    解体思路：还是利用层序遍历，只不过奇数的时候利用数组来颠倒一下顺序*/
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> arrayList=new ArrayList<>();
        if (pRoot==null)return arrayList;
        Queue<TreeNode> queue=new LinkedList<>();//定义队列用来实现层序遍历
        queue.offer(pRoot);//将根节点压入队列中
        int flg=1;//判断是那一层用不用颠倒顺序

        while (!queue.isEmpty()){
            int size=queue.size();//这个值代表当前层有多少个节点
            ArrayList<Integer> list1=new ArrayList<>();
            if (flg%2 == 0){
                int [] arr1=new int[size];//利用数组颠倒顺序
                while (size!=0){
                    TreeNode cur=queue.poll();
                    arr1[size-1]=cur.val;//将顺序全部存入数组中
                    if (cur.left!=null)queue.offer(cur.left);
                    if (cur.right!=null)queue.offer(cur.right);
                    size--;
                }
                for (int i = 0; i < arr1.length; i++) {
                    list1.add(arr1[i]);
                }
            }else{
                while (size!=0){
                    TreeNode cur=queue.poll();
                    list1.add(cur.val);
                    if (cur.left!=null)queue.offer(cur.left);
                    if (cur.right!=null)queue.offer(cur.right);
                    size--;
                }
            }
            flg++;
            arrayList.add(list1);
        }
        return arrayList;
    }
//    官话解法：利用反转，问题是我想到了反转但是我不知道Collections.reverse有这个函数，静态类的全部方法
    public ArrayList<ArrayList<Integer> > Print2(TreeNode pRoot) {
        TreeNode head = pRoot;
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
        if(head == null)
            //如果是空，则直接返回空list
            return res;
        //队列存储，进行层次遍历
        Queue<TreeNode> temp = new LinkedList<TreeNode>();
        temp.offer(head);
        TreeNode p;
        boolean flag = true;
        while(!temp.isEmpty()){
            //记录二叉树的某一行
            ArrayList<Integer> row = new ArrayList<Integer>();
            int n = temp.size();
            //奇数行反转，偶数行不反转
            flag = !flag;
            //因先进入的是根节点，故每层节点多少，队列大小就是多少
            for(int i = 0; i < n; i++){
                p = temp.poll();
                row.add(p.val);
                //若是左右孩子存在，则存入左右孩子作为下一个层次
                if(p.left != null)
                    temp.offer(p.left);
                if(p.right != null)
                    temp.offer(p.right);
            }
            //奇数行反转，偶数行不反转
            if(flag)
                Collections.reverse(row);
            res.add(row);
        }
        return res;
    }


   /* 求给定二叉树的最大深度，也就是求二叉树的高度
    6：深度是指树的根节点到任一叶子节点路径上节点的数量。
    解题思路：利用遍历来求*/
   public int maxDepth (TreeNode root) {
       if (root==null)return 0;
       int leftDepth=0;
       int rightDepth=0;
       //判断左树和右树的那个高度高，最后加上根节点的一层
       leftDepth=maxDepth(root.left);
       rightDepth=maxDepth(root.right);
       return leftDepth>rightDepth?leftDepth+1:rightDepth+1;
   }
   /*二叉树中和为某一值的路径(一)
    7：给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
    那肯定需要从根节点遍历到叶子，我们可以在根节点每次往下一层的时候，将sum减去节点值，最后检查是否完整等于0.
    而遍历的方法我们可以选取二叉树常用的递归前序遍历，因为每次进入一个子节点，更新sum值以后，
    当于对子树查找有没有等于新目标值的路径，

终止条件： 每当遇到节点为空，意味着过了叶子节点，返回。每当检查到某个节点没有子节点，它就是叶子节点，此时sum减去叶子节点值刚好为0，说明找到了路径。
返回值： 将子问题中是否有符合新目标值的路径层层往上返回。
本级任务： 每一级需要检查是否到了叶子节点，如果没有则递归地进入子节点，同时更新sum值减掉本层的节点值。
    */
    public boolean hasPathSum (TreeNode root, int sum) {
        //空节点找不到路径
        if(root == null)
            return false;
        //叶子节点，且路径和为sum
        if(root.left == null && root.right == null && sum - root.val == 0)
            return true;
        //递归进入子节点
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
   /* 对称的二叉树
   8: 给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
      解题思路：利用判断俩颗二叉树是不是相同二叉树的思路*/
    private boolean isSameTree(TreeNode p,TreeNode q){
        //判断一个节点为空和一个节点不为空的情况
        if (p == null && q!= null || p!=null && q== null)return false;
        //判断都是空的情况
        if (p== null && q==null)return true;
        if (p.val != q.val)return false;
        return isSameTree(p.left,q.right)&&isSameTree(p.right,q.left);

    }
    public boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot==null)return true;
        return isSameTree(pRoot.left,pRoot.right);
    }
   /* 合并二叉树
    9:已知两颗二叉树，将它们合并成一颗二叉树。
    并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。
    解题思路：不为空的时候将值加起来，为空的时候返回存在的节点，并直接赋予新节点凭借上去*/

    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {

        if (t1==null&&t2==null)return null;
        if (t1!=null&&t2==null)return t1;
        if (t1==null&&t2!=null)return t2;
        //剩下的情况就是，t1和t2都不为空
        else{
            t1.val=t1.val+ t2.val;
        }
        //递归的走左节点和右节点
        TreeNode newLeft=mergeTrees(t1.left,t2.left);
        TreeNode newRight= mergeTrees(t1.right,t2.right);
//        如果新new的节点不为空说明是一个存在一个不存在，不用管是谁的直接凭借上去
        if (newLeft!=null)t1.left=newLeft;
        if (newRight!=null)t1.right=newRight;
        return t1;
    }
    /*二叉树的镜像
    10:操作给定的二叉树，将其变换为源二叉树的镜像。
    解题思路:创建俩个新节点用来保存当前的左子树和右子树*/
    public TreeNode Mirror (TreeNode pRoot) {
        if (pRoot==null)return null;
        TreeNode newleft=Mirror(pRoot.left);
        TreeNode newright=Mirror(pRoot.right);
        pRoot.left=newright;
        pRoot.right=newleft;
        return pRoot;
    }
    /* 判断是不是二叉搜索树
    11：给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。
    解题思路：根据二叉搜索树的中序遍历是一个递增序列的特质，先递归到最左边然后依次判断是否有序
     */
    int pre = Integer.MIN_VALUE;
    //中序遍历
    public boolean isValidBST (TreeNode root) {
        if (root == null) return true;
        //先进入左子树
        if(!isValidBST(root.left)) return false;
        if(root.val < pre) return false;
        //更新最值
        pre = root.val;
        //再进入右子树
        return isValidBST(root.right);
    }
   /* 判断是不是完全二叉树
    12:给定一个二叉树，确定他是否是一个完全二叉树。
     解题思路：利用层序遍历的思想*/
    public boolean isCompleteTree (TreeNode root) {
        if (root==null)return true;
       Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if (cur==null)break;
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        for (int i = 0; i < queue.size(); i++) {
            if (queue.peek()!=null)return false;
            queue.poll();
        }
        return true;
    }
    /*判断是不是平衡二叉树
    13：输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
    解题思路：利用高度差《=1这一条性质和高度》=0这个性质*/
    private   int Height(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftHeight=Height(root.left);
        int rightHeight=Height(root.right);
        if (leftHeight>=0 && rightHeight>=0&& Math.abs(leftHeight-rightHeight)<=1){
            return Math.max(leftHeight,rightHeight)+1;
        }else {
            //说明不平衡
            return -1;
        }
    }
    public boolean IsBalanced_Solution(TreeNode root) {
       if (root==null)return false;
       return Height(root)>0;
    }
    /*二叉搜索树的最近公共祖先
    14：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
    （1）解题思路：一种是直接利用父亲节点（用栈来模拟父亲节点来实现。
    （2）解题思路：利用二叉搜索树的中序遍历是有序的这条性质来实现*/
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        if (root==null)return -1;
        if (root.val==p||root.val==q)return root.val;
        int newleft=lowestCommonAncestor(root.left,p,q);
        int newright=lowestCommonAncestor(root.right,p,q);

        if (newleft!=-1&&newright!=-1)return root.val;
        else if (newleft!=-1)return newleft;
        else return newright;
    }
    /*在二叉树中找到两个节点的最近公共祖先
    15:给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
    解题思路：上一个题是二叉搜索树一样样的代码都不用动无语中了*/
    public int lowestCommonAncestor2 (TreeNode root, int o1, int o2) {
        if (root==null)return -1;
        if (root.val==o1||root.val==o2)return root.val;
        int newleft=lowestCommonAncestor(root.left,o1,o2);
        int newright=lowestCommonAncestor(root.right,o1,o2);

        if (newleft!=-1&&newright!=-1)return root.val;
        else if (newleft!=-1)return newleft;
        else return newright;
    }
   /* 重建二叉树
    16：给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。*/
   public int preIndex = 0;

    public TreeNode createTreeByPandI(int[] preorder, int[] inorder,int inbegin,int inend) {

        if(inbegin > inend) {
            //如果满足这个条件  说明 没有左树 或者 右树了
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        //找到根在中序遍历的位置
        int rootIndex = findIndexOfI(inorder,inbegin,inend,preorder[preIndex]);
        if(rootIndex == -1) {
            return null;
        }
        preIndex++;
        //分别创建 左子树 和 右子树
        root.left = createTreeByPandI(preorder,inorder,inbegin,rootIndex-1);
        root.right = createTreeByPandI(preorder,inorder,rootIndex+1,inend);
        return root;
    }

    private int findIndexOfI(int[] inorder,int inbegin,int inend,int key) {

        for(int i = inbegin; i <= inend;i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null) return null;

        return createTreeByPandI(preorder,inorder,0,inorder.length-1);
    }
//    官话解法——看不明白
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        int n = pre.length;
        int m = vin.length;
        //每个遍历都不能为0
        if(n == 0 || m == 0)
            return null;
        //构建根节点
        TreeNode root = new TreeNode(pre[0]);
        for(int i = 0; i < vin.length; i++){
            //找到中序遍历中的前序第一个元素
            if(pre[0] == vin[i]){
                //构建左子树
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(vin, 0, i));
                //构建右子树
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(vin, i + 1, vin.length));
                break;
            }
        }
        return root;
    }

    /* 输出二叉树的右视图
    17:请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图*/
    public int[] solve (int[] xianxu, int[] zhongxu) {
        TreeNode root=reConstructBinaryTree(xianxu,zhongxu);
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        ArrayList<Integer> list=new ArrayList<>();

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size != 0) {
                TreeNode cur = queue.poll();
                if (size == 1) {
                    list.add(cur.val);
                }
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
                size--;
            }
        }
        int [] arr=new int[list.size()];

        for (int i = 0; i <list.size() ; i++) {
            arr[i]=list.get(i);
        }
        return arr;
    }
    /*序列化二叉树-不会
    18:请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，
    * 但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。 */
    /*public String Serialize(TreeNode root) {
        //将二叉树转换为字符串，层序遍历的结果
        if (root==null)return null;
        StringBuilder sb=new StringBuilder();
        return Ser(root,sb);
    }
    public String Ser(TreeNode root,StringBuilder sb){
        if (root==null)return null;
        //层序遍历
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            sb.append(cur.val);
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        return sb.toString();
    }
    private int DesL=0;
    public TreeNode Deserialize(String str) {
        if (str==null)return null;
        TreeNode root=new TreeNode(str.charAt(DesL));
        DesL++;
        root.left=Deserialize(str);
        root.left=Deserialize(str);
        return root;
    }*/
    /*二叉搜索树与双向链表
    19：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示
    解题思路：将二叉搜索树的左孩子转变成前驱，右孩子转变成后继*/
    private  TreeNode prev=null;
    private void  InOrder(TreeNode pCur){
        if (pCur == null)return;
        InOrder(pCur.left);
        pCur.left=prev;
        if (prev!=null){
            prev.right=pCur;
        }
        prev=pCur;
        InOrder(pCur.right);
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null)return null;
        InOrder(pRootOfTree);
        TreeNode head=pRootOfTree;
//        返回链表的头结点
        while (head.left!=null){
            head= head.left;
        }
        return head;

    }






















}

